package cn.springcloud.fix.demo.leecode;

import com.google.common.collect.Lists;

import java.util.*;

public class MaximalSquare {

    public static void main(String[] args) {
        int[] heights = new int[]{2, 1, 2};
        int res = trap(heights);
        System.out.println(res);

//        do {
//            Entry<K, V> next = e.next;
//            int i = indexFor(e.hash, newCapactiy);
//            e.next = newTable[i];
//            newTable[i] = e;
//            e = next;
//        } while (e != null);
    }

    // 接雨水
    public static int trap(int[] height) {
        int max = 0, leftMaxH = 0, rightMaxH = 0;

        int left = 0;
        int right = height.length - 1;

        while (left <= right) {
            if (leftMaxH <= rightMaxH) {
                leftMaxH = Math.max(leftMaxH, height[left]);
                max = max + (leftMaxH - height[left]);
                left++;
            } else {
                rightMaxH = Math.max(rightMaxH, height[right]);
                max = max + (rightMaxH - height[right]);
                right--;
            }
        }
        return max;
    }

//    void transfer(Entry[] newTable, boolean rehash) {
//        for (Entry<K, V> e : table) {
//            while (null != e) {
//                Entry<K, V> next = e.next;
//                e.next = newTable[i];
//                newTable[i] = e;
//                e = next;
//            }
//        }
//    }

    // 85. 最大矩形,https://leetcode-cn.com/problems/maximal-rectangle/
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) return 0;
        int column = matrix[0].length;
        int[][] dp = new int[row][column];
        for (int i = 0; i < row; i++)
            for (int j = 0; j < column; j++)
                if (matrix[i][j] == '1')
                    dp[i][j] = 1;

        for (int i = 1; i < row; i++)
            for (int j = 0; j < column; j++)
                if (dp[i - 1][j] >= 1 && dp[i][j] == 1)
                    dp[i][j] = dp[i - 1][j] + 1;

        int area = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (dp[i][j] == 0) continue;
                int curHeigth = dp[i][j];
                for (int k = j; k >= 0 && dp[i][k] != 0; k--) {
                    int curWidth = j - k + 1;
                    curHeigth = Math.min(curHeigth, dp[i][k]);
                    area = Math.max(area, Math.max(dp[i][k], curHeigth * curWidth));
                }
            }
        }
        return area;
    }

    // https://leetcode-cn.com/problems/maximal-square/
//    public static int maximalSquare(char[][] matrix) {
//        int col = matrix[0].length;
//        int row = matrix.length;
//
//        int[] heights = new int[col];
//        for (int i = 0; i < row; i++) {
//            char[] chars = matrix[i];
//            for (int j = 0; j < col; j++) {
//                if (chars[j] == '1') {
//                    heights[j] += 1;
//                } else {
//                    heights[j] = 0;
//                }
//            }
//            //....
//        }
//    }

    //这两种暴力方法的时间复杂度均为 O(N`2)
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) return 0;

        int res = 0;
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;
            int curHeight = heights[i];
            // 找左边最后 1 个大于等于 heights[i] 的下标
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }
            // 找右边最后 1 个大于等于 heights[i] 的索引
            while (right < len - 1 && heights[right + 1] >= curHeight) {
                right++;
            }
            int width = right - left + 1;
            res = Math.max(res, width * curHeight);
        }
        return res;
    }

    // https://blog.csdn.net/Zolewit/article/details/88863970
    public static int largestRectangleArea2(int[] heights) {
        // int length = heights.length;
        // if (length == 0) return 0;
        heights = Arrays.copyOf(heights, heights.length + 1);

        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                Integer num = stack.pop();
                int w = stack.isEmpty() ? i : i - num;
                int area = w * heights[num];
                maxArea = Math.max(maxArea, area);
            }
            stack.push(i);
        }

        return maxArea;
    }
}
